package com.leet.bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class NumsCourseTo {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 返回结果
        int[] ans = new int[numCourses];
        // inDegree，queue，segment（sqb）
        int[] inDegree = new int[numCourses];
        Queue<Integer> queue = new LinkedList<>();
        List<List<Integer>> segment = new ArrayList<>();
        // 给segment加链表
        for(int i = 0; i < numCourses;i++){
            segment.add(new LinkedList<>());
        }
        // 遍历二维prerequisites，初始化in
        for(int[] info: prerequisites){
            inDegree[info[0]]++;
            segment.get(info[1]).add(info[0]);
        }
        // 没有入度的节点入队
        for(int i = 0;i < numCourses;i++){
            if(inDegree[i] == 0){
                queue.offer(inDegree[i]);
            }
        }
        int count = 0;
        // 开始入队，出队,出队的时候把它放在ans里
        while(!queue.isEmpty()){
            // 队头
            Integer front = queue.poll();
            ans[count] = front;
            count++;
            // 根据front，通过segment映射到对应的链表，把它进入的inDegree--
            for (int arr:segment.get(front)){
                inDegree[arr]--;
                // 如果某个入度为0了，把它放进队列
                if(inDegree[arr] == 0) queue.offer(arr);
            }

        }
        // 完成的条件
        if(count == numCourses){
            return ans;
        }
        return new int[0];
    }
}
